﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


//关键是顺序不变
public class Solution300
{
    public int LengthOfLIS2(int[] nums)
    {
        int len = nums.Length;
        int max = 0;

        for (int start = 0; start < len; start++)
        {

            int i = start;
            int pre = nums[start];
            int sum = 1;
            while (i < len)
            {

                if (nums[i] > pre)
                {
                    sum++;
                    pre = nums[i];
                    Console.WriteLine("start   " + start + "   sum   " + sum + "   pre   " + pre);
                }
                i++;

               


            }

            max = Math.Max(max, sum);
        }
        return max;
    }

    //状态转移
    //dp[i]=dp[i-1]+1,ifnums[i]>nums[i-1]

    public int LengthOfLIS(int[] nums)
    {
        int len = nums.Length;
        int max = 0;

        int[] dp=new int[len];//以i结尾的子序列的长度
        dp[0] = 1;
        for (int start = 0; start < len; start++)
        {
            dp[start] = 1;

            for (int j = 0; j < start; j++)
            {
                if(nums[start] > nums[j])//序列长度加1
                {
                    dp[start]=Math.Max(dp[start], dp[j]+1);


                } 
         
            }


            max = Math.Max(max, dp[start]);
        }
        return max;
    }

}

class Program300
{


    static void Main300(string[] args)
    {


        Solution300 solution = new Solution300();
        //int[] nums = [10, 9, 2, 5, 3, 7, 101, 18];
        int[] nums = [0, 1, 0, 3, 2, 3];
        int res = solution.LengthOfLIS(nums);
        Console.WriteLine(res);
    }
}